package demo.practice.competition;

import java.util.*;

public class P5816_3 {

    public static void main(String[] args) {
        P5816_3 p5816 = new P5816_3();
        p5816.maxGeneticDifference(new int[]{-1, 0, 1, 1}, new int[][]{{0, 2}, {3, 2}, {2, 5}});
    }


    class Trie {
        Trie[] children = new Trie[2];
        int cnt = 0;
    }

    Trie root = new Trie();

    public void insert(int x) {
        Trie p = root;
        for (int i = 31; i >= 0; i--) {
            int u = (x >> i) & 1;
            if (p.children[u] == null) {
                p.children[u] = new Trie();
            }
            p = p.children[u];
            p.cnt++;
        }
    }

    public void remove(int x) {
        Trie p = root;
        for (int i = 31; i >= 0; i--) {
            int u = (x >> i) & 1;
            Trie next = p.children[u];
            p.children[u].cnt--;
            if (p.children[u].cnt == 0) {
                p.children[u] = null;
            }
            p = next;
        }
    }

    public int query(int x) {
        int res = 0;
        Trie p = root;
        for (int i = 31; i >= 0; i--) {
            int u = (x >> i) & 1;
            if (p.children[1 - u] != null) {
                res += 1 << i;
                p = p.children[1 - u];
            } else {
                p = p.children[u];
            }
        }
        return res;
    }

    public void dfs(int u) {
        insert(u);
        if (qs.containsKey(u)) {
            for (int[] q : qs.get(u)) {
                int v = q[0];
                int id = q[1];
                res[id] = query(v);
            }
        }
        for (int j : head.getOrDefault(u, Collections.emptyList())) {
            dfs(j);
        }
        remove(u);
    }

    Map<Integer, List<Integer>> head = new HashMap<>();
    Map<Integer, List<int[]>> qs = new HashMap<>();
    int[] res;

    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
        int root = -1;
        res = new int[queries.length];
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == -1) {
                root = i;
            } else {
                head.computeIfAbsent(parents[i], l -> new ArrayList<>()).add(i);
            }
        }
        for (int i = 0; i < queries.length; i++) {
            qs.computeIfAbsent(queries[i][0], l -> new ArrayList<>()).add(new int[]{queries[i][1], i});
        }
        dfs(root);
        return res;
    }
}
